package class5;

import common.TreeNode;
import common.TreeNodeUtils;

/**
 * 110. 平衡二叉树
 * 给定一个二叉树，判断它是否是平衡二叉树
 * 平衡二叉树（Balanced Binary Tree）通常指的是高度平衡的二叉树，其中任意一个节点的左子树和右子树的高度差不超过1。
 * 具体来说，二叉树的每个节点的左右子树的高度差的绝对值不超过1。
 * +        1
 * +      /   \
 * +     2      3
 * +      \    /  \
 * +      4   5    6
 * +     / \   \    \
 * +    7   8   9    10
 * +     \ /
 * +    11 12
 * <p>
 * 判断二叉树是否平衡的核心思路：
 * 1.递归遍历树的每个节点，对于每个节点，计算其左右子树的高度。
 * 2.判断左右子树的高度差是否超过1，如果超过1，则返回不平衡。
 * 3.如果左右子树高度差不超过1，继续递归检查其左右子树。
 */
public class Code07_BalanceBinaryTree {

    public static void main(String[] args) {

        TreeNode treeNode1 = TreeNodeUtils.getNoBalanceTree();
        System.out.println(isBalance(treeNode1));
    }

    public static boolean isBalance(TreeNode root) {
        return process(root).isBalanced;
    }

    // 以某个节点头的时候， 1) 整棵树是否平 2）整棵树的高度是多少
    public static class Info {
        public boolean isBalanced;
        public int height;

        public Info(boolean isBalanced, int height) {
            this.isBalanced = isBalanced;
            this.height = height;
        }
    }

    private int isBalance2(TreeNode node) {
        // 空节点高度为0
        if (node == null) {
            return 0;
        }

        // 递归计算左子树的高度
        int leftHeight = isBalance2(node.left);
        // 如果左子树不平衡，直接返回-1
        if (leftHeight == -1) {
            return -1;
        }

        // 递归计算右子树的高度
        int rightHeight = isBalance2(node.right);
        // 如果右子树不平衡，直接返回-1
        if (rightHeight == -1) {
            return -1;
        }

        // 如果当前节点的左右子树高度差超过1，则不平衡，返回-1
        if (Math.abs(leftHeight - rightHeight) > 1) {
            return -1;
        }

        // 当前节点的高度是左右子树高度的最大值 + 1
        return Math.max(leftHeight, rightHeight) + 1;
    }

    public static Info process(TreeNode x) {
        /**
         * 当x ==null时，树的高度为0
         */
        if (x == null) {
            return new Info(true, 0);
        }
        // 左树是否平衡
        Info leftInfo = process(x.left);
        Info righInfo = process(x.right);

        // 左树和右树的高度的最大高度+1，就是当前节点的高度
        int height = Math.max(leftInfo.height, righInfo.height) + 1;

        /**
         * 1.左右子树均为平衡树
         * 2.左右子树的高度差也不大于1，则本节点也处于平衡状态
         */
        boolean isBalanced = leftInfo.isBalanced && righInfo.isBalanced && Math.abs(leftInfo.height - righInfo.height) < 2;
        return new Info(isBalanced, height);
    }
}


